Data broadcast over a network involves sending data from one sender across a network to multiple receivers. In data broadcast all of the receivers should receive substantially the same data. An example of broadcasting, though not necessarily over a network, is television broadcasting. In television broadcasting one television station (a sender) broadcasts data to multiple people with televisions (each a receiver).
There are many networks over which a sender may broadcast data to multiple receivers. One network is a physical network, such as ISPs (Internet Service Providers) on the Internet. This type of physical network includes routers, wires, and other hardware. Other networks include overlay networks on top of a physical network. Here nodes of the network include people's computers, computer servers, other logic machines, or the like.
FIG. 1 sets forth a simple model of a sender sending data across a communication network to multiple receivers. FIG. 1 shows a sender 102 sending data to a first receiver 104, a second receiver 106, and a third receiver 108. The sender 102 sends the data across a communication network 110. For purpose of clarity the sender 102 and the receivers 104, 106, and 108 are shown outside of the communication network 110. Each of these, however, may be modeled as a node within the communication network 110, as will be shown below.
The communication network 110 includes nodes. These nodes may be routers, client computers, and server computers. These nodes route, send, and/or receive data.
FIG. 2 sets forth a simple model of the communication network 110 having four intermediate nodes and nine communication paths as well as nodes representing the sender 102, the first receiver 104, and the second receiver 106.
The four intermediate nodes include a first node 202, a second node 204, a third node 206, and a fourth node 208. The sender 102 may include or be co-located with an intermediate node, though for simplicity this is not shown. Also, the receivers 104 and 106 may include or be co-located with an intermediate node, also not shown for simplicity. The communication paths (which may be physical or otherwise) are paths of communication between the sender 102, the intermediate nodes, the first receiver 104, and/or the second receiver 106. These communication paths are also referred to as “edges”.
There are two typical ways in which senders broadcast data over a network. One way is called unicast. In unicasting, a sender sends data to each receiver. The problem with unicasting is that you have to dedicate a different path (with all the applicable resources) to every receiver. Because of this, unicasting may require as many resources as are used sending data from one sender to one receiver for each of the multiple receivers. Thus, it uses a great deal of bandwidth, making it an expensive way to send data to multiple receivers.
The second, and better, way to broadcast data over networks is called multicast. Multicasting is a more common way to broadcast data. In multicasting, a distribution tree is set up to transmit data through a network from a source (the root of the tree) to receivers (at leaves of the tree). Each node in the distribution tree simply copies data from its inbound link to one or more outbound links. Multicast results in a single path of data from the source to each receiver. One problem with multicasting, however, is that it has a limited throughput to each receiver, as shown in FIG. 3.
FIG 3 sets forth simple models of the communication network 110, similar to that shown in FIG. 2. Here again, there is the sender 102 (marked with an “s”) and the first and second receivers 104 and 106 (marked with “r1” and “r2”). Each edge has a particular capacity for communicating data. In this example, each edge capacity equals a “unit”, for simplicity. As shown in a first-receiver-only multicast model 302 and a second-receiver-only multicast model 304, the maximum throughput to each receiver (separately) is two units. The maximum throughput to the receiver 104 is two units and the maximum throughput to the second receiver 106 is also two units—but not if the sender 102 is sending data to both of the receivers 104 and 106.
As shown in a multicast model 306, the sender 102 may broadcast one unit of throughput to the receivers 104 and 106, using a combination of a top path in the model 302 (from the sender 102 to the first receiver 104 through just the first intermediate node 202) and a top path in the model 304 (from the sender 102 to the second receiver 106 through the intermediate nodes 202, 206, and 208). It would also be possible to use a combination of the top path in the model 302 with a bottom path in the model 304 (from the sender 102 to the second receiver 106 through just the second intermediate node 204), or a bottom path in the model 302 (from the sender 102 to the first receiver 104 through the intermediate nodes 204, 206, and 208) with the bottom path in the model 304, but not the bottom path in the model 302 and the top path in the model 304. However, the sender 102 cannot broadcast two units of throughput to the receivers 104 and 106. For the sender 102 to broadcast two units of throughput to receivers 104 and 106, it would have to use both paths in both of the models 302 and 304. Thus, the edge from the third node 206 to the fourth node 208 would have to have a capacity of two units. Edges, however, have a capacity of one unit, not two. Thus, the sender 102, with this model 306, cannot broadcast two units of throughput to the receivers 104 and 106.
At best, with multicasting, the sender 102 may broadcast one unit of throughput to both of the receivers 104 and 106, and one unit of additional throughput to either the receiver 104 or receiver 106, but not both.
Thus, with multicasting it is not possible to broadcast two units of throughput to both receivers 104 and 106 simultaneously, because the maxflow (i.e., maximum-throughput) paths to each receiver collide (e.g., at the edge between intermediate nodes 206 and 208).
For more data on this failure of multicasting, see Alswede, Cai, Li, and Yeung, “Network information flow,” IEEE Trans. Information Theory, IT-46, pp. 1204-1216, July 2000.
Recently, performing operations (called “encoding” when performed and “decoding” when reversed) at nodes of a communication network has been discussed; it is called “network coding.” With network coding, more data may be received by the receivers (called additional “throughput”) compared to unicasting and multicasting. In network coding, encoding may be performed at potentially any node in the network as data traverses through the network. In unicast and multicast, the data is simply forwarded or replicated; it is not encoded at the intermediate nodes in the network. Network coding is not just an operation performed to add redundancies, such as sometimes done in unicast and multicast—it actually increases throughput.
Thus, this network coding solution may increase the maximum throughput over multicasting and unicasting.
For instance, suppose Ci is the capacity, i.e., the maximum throughput, available to the receiver 104, as determined by the maxflow-mincut theorem. (For more data on this theorem, see L. R. Ford, Jr., and D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962). Thus, Ci=2 for each receiver in the above example. Theoretically (see Alswede et al., supra), it is possible to broadcast to all receivers simultaneously a number of units of throughput equal to the minimum of the capacities to each receiver, that is, equal to the “broadcast capacity” C=min Ci, using network coding.
To increase throughput over the conventional methods, network coding encodes data at some or all of the internal nodes in a communication network, as the following figure shows.
FIG. 4 sets forth, a simple network-coding model 400 of the communication network 110, similar to those shown in FIGS. 2 and 3. Here again, there is the sender 102, the first and second receivers 104 and 106, and the intermediate nodes 202, 204, 206, and 208. In this figure, data a and b is broadcast to both receivers. The third node 206 of the communication network 110 encodes the received a and b by adding a and b over a finite field. (Various other linear combinations could also be used.) The third node 206 then propagates this data downstream. The receiver 104 recovers (i.e., “decodes”) a and b from a and a+b by subtracting a from a+b. The receiver 106 recovers (i.e., “decodes”) a and b from a+b and b, similarly by subtracting b from a+b. Thus, with network coding, the receivers 104 and 106 both may receive two units of data. Each of these pieces of data, b, a, and a+b, are referred to generically as “symbols.”
Here the encoding functions performed at the internal nodes in the network as well as the decoding functions performed at the receivers may be, in general, linear functions of data over a finite field. This is sufficient, i.e., linear functions over a finite field are sufficient at the internal nodes and at the receivers for the broadcast capacity to be achieved. (For more data on this sufficiency, see Li and Yeung, “Linear network coding,” IEEE Trans. Information Theory, IT-49, pp 371-381, February 2003). (A finite field is a number system with only a finite number of elements, with addition, subtraction, multiplication, and division well defined.)
Those skilled in the art of network coding have discussed the possibility of providing a way to design linear encoding functions at each internal node as well as linear decoding functions at each potential receiver. (For a discussion on this, see Koetter and Médard, “An algebraic approach to network coding,” Proc. INFOCOM, 2002). Others have, furthermore, provided polynomial time algorithms to design the linear encoding and decoding functions. (For a discussion on this, see Jaggi, Jain, and Chou, “Low complexity optimal algebraic multicast codes,” IEEE Int'l Symp. on Information Theory, Yokohama, June 2003; Sanders, Egner, and Tolhuizen, “Polynomial time algorithms for linear information flow,” ACM Symp. on Parallelism in Algorithms and Architectures, San Diego, June 2003; and Jaggi, Sanders, Chou, Effros, Egner, Jain, and Tolhuizen, “Polynomial time algorithms for network code construction,” IEEE Trans. Information Theory, submitted for possible publication, 2003, currently found at: http://www.its.caltech.edu/≠jaggi/pubs/index.html). They show that field size T suffices, where T is the number of receivers. (For a discussion on this, see Jaggi, Sanders, et al., supra). Others also show that linear encoding functions may be designed randomly, and that if the field size is at least E/δ, where E is the number of edges and δ is any number greater than zero, then the encoding will be invertible at any given receiver with probability at least 1−δ. Furthermore, if the field size is at least ET/δ, then the encoding will be invertible simultaneously at all receivers with probability at least 1−δ.
One problem with the current theoretical discussion on network coding is that it assumes global knowledge of the network's structure, or “topology.” That is, the current discussion assumes that some entity knows about each node in the network and how they are connected. This discussion assumes this global knowledge of the network topology because it provides a way to address two problems: 1) computing the broadcast capacity (so that the source knows the data rate at which to send), and 2) designing the linear decoding functions (so that each decoder knows how to invert the linear encoding functions applied at the internal nodes).
The prior art discussions also usually assume that the encoding and decoding functions must somehow be distributed reliably to the interior nodes and to the receivers. Thus, each node is assumed to be known and then told what operation to perform on the data.
Reliable distribution of the encoding functions to the interior nodes, however, may be avoided if they are chosen randomly or otherwise independently. In that case, the local encoding vectors as well as the topology must be known at the receivers in order for the receivers to compute the linear decoding functions to invert the symbols into their original form (here a and b), or they must be known at some centralized location that may reliably distribute the computed decoding functions to the receivers. Another problem with not knowing a network's topology is that if it changes, or if the model of the topology is wrong, the receivers will not be able to decode all of the symbols received.
Prior attempts have been made to design encoding functions for a class of failure patterns so that capacity is not reduced below a certain amount. But then the decoders still need to know the failure pattern in order to compute and apply the proper linear decoding function. For this purpose, communicating the failure pattern to the decoders must be done reliably. This data grows with the number of failed links.
Prior art discussions also usually assume that the communication is synchronous throughout the network. That is, symbols arrive at, are processed in, and are sent out from every node synchronously, according to a network-wide heartbeat. In most of today's packet networks, however, this is infeasible. Nodes in a packet network operate asynchronously with each other. Furthermore, in most of today's packet networks, transmission capacities along each edge vary as competing communication processes begin and end, and the network becomes more or less congested. For the above reasons, symbols may not arrive at any node in a synchronous fashion, and hence may not be processed and sent out in a synchronous fashion.